Processing math: 100%

POI2013 Price List

POI
双向链表, 最短路

POI2013 Price List

题目大意：

给定一个无向图，边权均为a，然后将原图中满足最短路等于2a的点对(x,y)之间再加一条边权为b的边。求k的单源最短路。

PS.各种乱搞，写不出来，只好膜题解。

题解：

不难想到的是，最短路只会是以下几种情况：

  1. 直接在原图上走最短路。
  2. 原图最短路，每两条边合并成一个b。(若长度为奇数，还要补一个a)
  3. 如果按2中的方案走，长度为奇数的路径是要补a的，但倘若a很大的话，那就不划算了。因而可以在原图上找到一种稍长的、但可以保证完美缩成若干b的路线，这样反而可以更短。

前两种情况比较好处理，直接跑最短路就可以了。由于边权都是a，因而可以直接用BFS，此时的复杂度为O(m).

但第三种情况就不太好搞了，但我们可以尝试先写出暴力。

也可以用BFS。

对于当前出队列的点p，先向外扫描一圈把与之相邻的节点标记掉。（表示这些节点不能从p转移到。）此时disp为偶数个a，因而相邻节点与s的最短路(这里指可以被分为若干个b的最短路)，是不可以从p转移过来的。

之后对于每一个相邻节点，再搜它们的相邻节点，没有被标记的，且未被更新过的dis的节点入队列，并更新其dis(由p更新，p到它的最短路为2a，可以将其缩为一个b)。

最后要把与p相邻的节点的标记去掉。(因为可能以后会有别的点可以来更新它)

这样即可达到我们想要的效果，复杂度为O(m2)。

但这样显然过不了，我们考虑优化。

取出队列开头的p后，遍历与它相邻的点的过程，我们称之为一次遍历。然后再遍历第二波节点，我们称之为二次遍历。

当一次遍历到一个节点pp以后，并由pp扩展到下一个节点to时，我们发现(pp,to)这一条边在以后的二次遍历中再也没有用了。因为to已经进入了队列，而pp没有，也就是说pp还有机会成为一次遍历产生的点，这时再由它第二次遍历时，原来已经进入队列的to就不需要再次进入了，所以该边可以删掉。(这里的删掉只是指在二次遍历中删掉，一次遍历还可能用到这些边)

因而我们一次遍历用原图的边，二次遍历的边可以不停地删掉。

对于删边的操作，我们可以用双向链表来存边已达到效果。

接下来我们分析一下复杂度：

首先，时间复杂度约等于遍历边的数量，所以我们只需要考虑那些遍历了却没有删掉的边的数量。

对于每一个节点x，由它开始进行一次遍历、再二次遍历中，没被删掉的边只有一种，就是在二次遍历中遍历到了一个与x距离为1的点，也就是说形成了一个三元环。所以对于这个节点x，假设和它距离为1的点有k个，那么这次最多有k2条边被遍历了但没有删掉。又因为总共的边数为m，所以总的时间复杂度为:

∑v∈Vmin(degree(v2),m)≤∑v∈V√degree(v2)∗m≤∑v∈Vdegree(v)∗√m=O(m√m)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<queue>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
/////////////////////////////////////////////////////////
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
/////////////////////////////////////////////////////////
const int N=100001;
/////////////////////////////////////////////////////////
struct EDGE{
	int tot_edge,head[N];
	struct Edge{
		int to,pre,nxt;
	}edge[N<<1];
	void add_edge(int a,int b){
		if(~head[a])edge[head[a]].pre=tot_edge;
		edge[tot_edge]=(Edge){b,-1,head[a]};
		head[a]=tot_edge++;
	}
	void del_edge(int p,int id){
		if(id==head[p])head[p]=edge[id].nxt;  
		if(~edge[id].nxt)edge[edge[id].nxt].pre=edge[id].pre;
		if(~edge[id].pre)edge[edge[id].pre].nxt=edge[id].nxt;
	}
}E1,E2;
/////////////////////////////////////////////////////////
int n,m,s,A,B;
/////////////////////////////////////////////////////////
int dis[N];
queue<int>Q;
void BFS(){
	while(!Q.empty())Q.pop();
	memset(dis,-1,sizeof(dis));
	dis[s]=0;Q.push(s);
	while(!Q.empty()){
		int p=Q.front();Q.pop();
		for(int i=E1.head[p];~i;i=E1.edge[i].nxt){
			int to=E1.edge[i].to;
			if(dis[to]==-1)dis[to]=dis[p]+1,Q.push(to);
		}
	}
}
/////////////////////////////////////////////////////////
int dis1[N];
bool mark[N];
void BFS1(){
	while(!Q.empty())Q.pop();
	memset(dis1,-1,sizeof(dis1));
	memset(mark,0,sizeof(mark));
	dis1[s]=0;mark[s]=true;Q.push(s);
	while(!Q.empty()){
		int p=Q.front();Q.pop();
		for(int i=E1.head[p];~i;i=E1.edge[i].nxt){
			int to=E1.edge[i].to;
			mark[to]=true;
		}
		for(int i=E1.head[p];~i;i=E1.edge[i].nxt){
			int pp=E1.edge[i].to;
			for(int j=E2.head[pp];~j;j=E2.edge[j].nxt){
				int to=E2.edge[j].to;
				if(!mark[to]&&dis1[to]==-1){
					dis1[to]=dis1[p]+2;
					mark[to]=true;
					Q.push(to);
					E2.del_edge(pp,j);
				}
			}
		}
		for(int i=E1.head[p];~i;i=E1.edge[i].nxt){
			int to=E1.edge[i].to;
			mark[to]=false;
		}
	}
}
int main(){
	memset(E1.head,-1,sizeof(E1.head));
	memset(E2.head,-1,sizeof(E2.head));
	Rd(n),Rd(m),Rd(s),Rd(A),Rd(B);
	for(int i=1,a,b;i<=m;i++){
		Rd(a),Rd(b);
		E1.add_edge(a,b);
		E1.add_edge(b,a);
		E2.add_edge(a,b);
		E2.add_edge(b,a);
	}
	BFS();
	BFS1();
	for(int i=1;i<=n;i++){
		int res=1<<30;
		if(~dis[i])res=min(dis[i]/2*B+dis[i]%2*A,dis[i]*A);
		if(~dis1[i])res=min(res,dis1[i]/2*B);
		printf("%d\n",res);
	}
	return 0;
}
分享到 评论